搭积木

[编程题]搭积木

热度指数：18547 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 50M，其他语言100M
算法知识视频讲解

小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？

定义每一个长方形的长 L 和宽 W ，袋子里面长方形的个数为 n 。

假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。

数据范围：长方形个数满足 $1 \le n \le 10^6 \$ ， $1 \le w \le l \le 2^{31}-1 \$

输入描述:

第一行为积木的总个数 N

之后一共有N行，分别对应于每一个积木的宽W和长L

输出描述:

输出总共可以搭的层数

示例1

输入

输出

算法知识视频讲解

Python 3

up_zhang

import bisect
while True:
    try:
        n = int(input())
        jimu_list = []
        for _ in range(n):
            l, w = map(int, input().split())
            jimu_list.append((l, w))
        # 先按照长 由小到大排序 在此基础上只需要判断宽的最长递增子序列即可
        jimu = list(sorted(jimu_list, key=lambda x: x[0]))
        a = []
        for jimu_info in jimu:
            index = bisect.bisect_right(a, jimu_info[1])
            if index == len(a):
                a.append(jimu_info[1])
            else:
                a[index] = jimu_info[1]
        print(len(a))
        
    except:
        break

发表于 2022-01-20 18:31:13 回复(0)